package com.cctc.juc.source.Bitc.Faqs;

import sun.misc.Unsafe;

import java.util.concurrent.locks.LockSupport;

/**
 * [AQS（Abstract Queued Synchronizer）抽象队列同步器]
 * 要求：[（熟练）手撕] 核心逻辑代码。
 * 同步线程 {排队演变过程}：
 * 1. t1, acquire(arg) -> [第一次] tryAcquire(arg) 成功，占用同步资源（state） 1 个小时，此时的同步队列为： head = tail = null；
 * 2. t2, acquire(arg) -> [第一次] tryAcquire(arg) 失败，addWaiter(mode) -> enq(t2)[懒加载：初始化同步队列] -> acquireQueued(t2) -> [第二次] tryAcquire(arg) 失败 -> park(t2)，此时的同步队列为 head(new Node()) [SIGNAL] <-> node[t2]；
 * 3. t3、t4、t5...，同上，此时的同步队列为 head(new Node()) [SIGNAL] <-> node[t2] [SIGNAL] <-> node[t3] [SIGNAL] <-> node[t4] [SIGNAL] <-> node[t5] [SIGNAL]...；
 * 4. 1 小时时间到，t1 释放同步资源（state），release(arg) -> tryRelease(arg) 成功 -> unparkSuccessor(head) 唤醒后继节点 t2 ->  acquireQueued(t2) -> [第二次] tryAcquire(arg) 成功 -> setHead(t2)，此时的同步队列为 head(node[t2]) [SIGNAL] <-> node[t3] [SIGNAL] <-> node[t4] [SIGNAL] <-> node[t5] [SIGNAL]...；
 * 5. 排队过程中，t3 意外终止，退出 acquireQueued(t3) -> cancelAcquire(t3)，此时的同步队列为 head(node[t2]) [SIGNAL] <-> node[t3] [CANCELLED] <-> node[t4] [SIGNAL] <-> node[t5] [SIGNAL]...；
 * 6. 1 小时时间到，t2 释放同步资源（state），release(arg) -> tryRelease(arg) 成功 -> unparkSuccessor(t2) 唤醒后继有效节点 t4 ->  acquireQueued(t4) -> [第二次] tryAcquire(arg) 成功 -> setHead(t4)，，此时的同步队列为 head(node[t4]) [SIGNAL] <-> node[t5] [SIGNAL]...；
 * 依据以上 AQS 线程同步过程，熟练手撕 AQS 核心逻辑代码。
 */
public abstract class AQS {
    static final class Node {
        volatile Thread waiter;
        volatile Node prev, next;
        Node nextWaiter;
        static final Node SHARED = new Node();
        static final Node EXCLUSIVE = null;
        volatile int waitStatus;
        static final int CANCELLED = 1, SIGNAL = -1, CONDITION = -2, PROPAGATE = -3;

        Node() {
        }

        public Node(Thread waiter, Node mode) {
            this.waiter = waiter;
            this.nextWaiter = mode;
        }

        public Node(Thread waiter, int waitStatus) {
            this.waiter = waiter;
            this.waitStatus = waitStatus;
        }

        final boolean isShared() {
            return nextWaiter == SHARED;
        }

        final Node predcessor() throws NullPointerException {
            Node p;
            if ((p = prev) == null) throw new NullPointerException();
            return p;
        }
    }

    private volatile transient Node head, tail;
    private volatile int state;

    protected AQS() {
    }

    public final void acquire(int arg) {
        if (!tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) {
            selfInterrupt();
        }
    }

    public final boolean release(int arg) {
        if (tryRelease(arg)) {
            Node h = head;
            if (h != null && h.waitStatus != 0) unparkSuccessor(h);
            return true;
        }
        return false;
    }

    protected boolean tryAcquire(int arg) {
        throw new UnsupportedOperationException();
    }

    protected boolean tryRelease(int arg) {
        throw new UnsupportedOperationException();
    }

    private Node addWaiter(Node mode) {
        Node node = new Node(Thread.currentThread(), mode);
        Node prev = tail;
        if (prev != null) {
            node.prev = prev;
            if (casTail(prev, node)) {
                prev.next = node;
                return node;
            }
        }
        enq(node);
        return node;
    }

    private Node enq(Node node) {
        for (; ; ) {
            Node prev = tail;
            if (prev == null) {
                if (casHead(new Node())) tail = head;
            } else {
                node.prev = prev;
                if (casTail(prev, node)) {
                    prev.next = node;
                    return node;
                }
            }
        }
    }

    private final boolean acquireQueued(Node node, int arg) {
        boolean failed = true;
        try {
            boolean interrupted = false;
            for (; ; ) {
                final Node prev = node.predcessor();
                if (prev == head && tryAcquire(arg)) {
                    setHead(node);
                    prev.next = null;
                    failed = false;
                    return interrupted;
                }
                if (shouldParkAfterFailedAcquire(prev, node) &&
                        parkAndCheckInterrupt()) {
                    interrupted = true;
                }
            }
        } finally {
            if (failed) cancelAcquire(node);
        }
    }

    private void setHead(Node node) {
        head = node;
        node.waiter = null;
        node.next = null;
    }

    private static boolean shouldParkAfterFailedAcquire(Node prev, Node node) {
        int waitStatus = prev.waitStatus;
        if (waitStatus == Node.SIGNAL) return true;
        if (waitStatus > 0) {
            do {
                node.prev = prev = prev.prev;
            } while (prev.waitStatus > 0);
            prev.next = node;
        } else {
            casWaitStatus(prev, waitStatus, Node.SIGNAL);
        }
        return false;
    }

    private boolean parkAndCheckInterrupt() {
        LockSupport.park(this);
        return Thread.interrupted();
    }

    private void cancelAcquire(Node node) {
        if (node == null) return;
        node.waiter = null;
        node.waitStatus = Node.CANCELLED;
        Node prev = node.prev;
        while (prev.waitStatus > 0) node.prev = prev = prev.prev;
        Node prevNext = prev.next;
        if (node == tail && casTail(node, prev)) casNext(prev, prevNext, null);
        else {
            int waitStatus;
            if (prev != head && ((waitStatus = prev.waitStatus) == Node.SIGNAL || (waitStatus <= 0 && casWaitStatus(prev, waitStatus, Node.SIGNAL))) && prev.waiter != null) {
                Node next = node.next;
                if (next != null && next.waitStatus <= 0) casNext(prev, prevNext, next);
            } else unparkSuccessor(prev);
            node.next = node;
        }
    }

    static void selfInterrupt() {
        Thread.currentThread().interrupt();
    }

    private void unparkSuccessor(Node head) {
        int waitStatus = head.waitStatus;
        if (waitStatus < 0) casWaitStatus(head, waitStatus, 0);
        Node next = head.next;
        if (next == null || next.waitStatus > 0) {
            next = null;
            for (Node t = tail; t != null && t != head; t = t.prev) {
                if (t.waitStatus <= 0) next = t;
            }
        }
        if (next != null) LockSupport.unpark(next.waiter);
    }

    // --- [CAS 操作] --- //
    private static final Unsafe UNSAFE = Unsafe.getUnsafe();
    private static final long headOffset, tailOffset;
    private static final long stateOffset;
    private static final long nextOffset;
    private static final long waitStatusOffset;

    static {
        Class<AQS> aqsClass = AQS.class;
        Class<Node> nodeClass = Node.class;
        try {
            headOffset = UNSAFE.objectFieldOffset(aqsClass.getDeclaredField("head"));
            tailOffset = UNSAFE.objectFieldOffset(aqsClass.getDeclaredField("tail"));
            stateOffset = UNSAFE.objectFieldOffset(aqsClass.getDeclaredField("state"));
            nextOffset = UNSAFE.objectFieldOffset(nodeClass.getDeclaredField("next"));
            waitStatusOffset = UNSAFE.objectFieldOffset(nodeClass.getDeclaredField("waitStatus"));
        } catch (NoSuchFieldException e) {
            throw new RuntimeException(e);
        }
    }

    private final boolean casHead(Node update) {
        return UNSAFE.compareAndSwapObject(this, headOffset, null, update);
    }

    private final boolean casTail(Node expect, Node update) {
        return UNSAFE.compareAndSwapObject(this, tailOffset, expect, update);
    }

    protected final boolean casState(int expect, int update) {
        return UNSAFE.compareAndSwapInt(this, stateOffset, expect, update);
    }

    protected int getState() {
        return state;
    }

    private final boolean casNext(Node target, Node expect, Node update) {
        return UNSAFE.compareAndSwapObject(target, nextOffset, expect, update);
    }

    private static final boolean casWaitStatus(Node target, int expect, int update) {
        return UNSAFE.compareAndSwapInt(target, waitStatusOffset, expect, update);
    }

}
